Data compression is an extremely useful tool for storing and transmitting large amounts of data. For example, the time required to transmit an image, such as a facsimile transmission of a document, is reduced drastically when compression is used to decrease the number of bits required to recreate the image.
Many different data compression techniques exist in the prior art. Compression techniques can be divided into two broad categories, lossy coding and lossless coding. Lossy coding involves coding that results in the loss of information, such that there is no guarantee of perfect reconstruction of the original data. The goal of lossy compression is that changes to the original data are done in such a way that they are not objectionable or detectable. In lossless compression, all the information is retained and the data is compressed in a manner which allows for perfect reconstruction.
In lossless compression, input symbols are converted to output codewords. If the compression is successful, the codewords are represented in fewer bits than the number of input symbols. Lossless coding methods include dictionary methods of coding (e.g., Lempel-Ziv), run length encoding, enumerative coding and entropy coding. For more information on run length coding, see H. Meyr, H. G. Roskolsky, and T. S. Huang, "Optimum Run Length Codes," IEEE Transactions on Communications, Vol. COM-22, No. 6, June 1974, pgs. 826-835. See also G. G. Langdon, Jr., "An Adaptive Run-Length Coding Algorithm," IBM Technical Disclosure Bulletin, Vol. 26, No. 7B, December 1983, pgs. 3783-3785 (A coding system using R2(k) codes for dynamically variable k values is attributed to Langdon). See S. W. Golomb, Run-Length Encoding, IEEE Trans., IT-12, (July 1966), pg. 399. For more information regarding run length codes and their use in conjunction with facsimile transmission, see M. Takagi and T. Tsuda, "A Highly Efficient Run-Length Coding Scheme For Facsimile Transmission," Electronics and Communications in Japan, Vol. 58-A, No. 2, 1975, pgs. 30-38. See also U.S. Pat. No. 4,325,085, entitled "Method and Apparatus for Adaptive Facsimile Compression Using a Two Dimensional Maximum Likelihood Predictor" (R. P. Gooch), issued Apr. 13, 1982.
Entropy coding consists of any method of lossless (i.e., perfect reconstruction is possible) coding which attempts to compress data close to the entropy limit using known or estimated symbol probabilities. Entropy codes include Huffman codes, arithmetic codes and binary entropy codes. Huffman coding uses a fixed length to variable length code which produces an integral number of bits for each symbol. However, Huffman coding cannot code symbols with less than one bit and, thus, cannot efficiently represent single symbols with probabilities of greater than 50%. Arithmetic coders are based on theoretical coding techniques involving infinite precision floating point numbers. However, arithmetic coders can only be implemented with finite precision arithmetic so their coding efficiency is reduced from the theoretical maximum. Practical arithmetic coders, such as the Q-coder of International Business Machines (IBM), use additional techniques that result in faster software or less hardware at the expense of compression efficiency. The Q-coder is a binary arithmetic coder in which additions have been substituted for multiplications, probabilities are limited to discrete values, and probability estimates are updated when bits are output.
Binary entropy coders are lossless (i.e., perfect reconstruction is possible) coders which act only on binary (yes/no) decisions, often expressed as the most probable symbol (MPS) and the least probable symbol (LPS). Examples of binary entropy coders include IBM's Q-coder and a coder referred to as the B-coder. The B-coder is a binary entropy coder which uses a finite state machine for compression. For more information on the B-coder, see co-pending application Ser. No. 07/931,156, entitled "Method and Apparatus For Entropy Coding" filed Aug. 17, 1992.
FIG. 1 shows a block diagram of a prior art compression/decompression system using a binary entropy coder. For coding, data is input into context model (CM) 101. CM 101 translates the input data into a set or sequence of binary decisions and provides the context bin for each decision. Both the sequence of binary decisions and their associated context bins are output from CM 101 to the probability estimation module (PEM) 102. PEM 102 receives each context bin and generates a probability estimate for each binary decision. The actual probability estimate is typically represented by a class, referred to as PClass. Each PClass is used for a range of probabilities. PEM 102 also determines whether the binary decision (result) is or is not in its more probable state (i.e., whether the decision corresponds to the MPS). The bit-stream generator (BG) module 103 receives the probability estimate (i.e., the PClass) and the determination of whether or not the binary decision was likely as inputs. In response, BG module 103 produces a compressed data stream, outputting zero or more bits, to represent the original input data.
For decoding, CM 104 provides a context bin to PEM 105, and PEM 105 provides the probability class (PClass) to BG module 106 based on the context bin. BG module 106 is coupled to receive the probability class. In response to the probability class, BG module 106 returns a bit representing whether the binary decision (i.e., the event) is in its most probable state. PEM 105 receives the bit, updates the probability estimate based on the received bit, and returns the result to CM 104. CM 104 receives the returned bit and uses the returned bit to generate the original data and update the context bin for the next binary decision.
The context model is typically application specific. Since any type of data can be reduced to bits, a binary entropy coder with the proper context model can be used for any data. An example of a context model is given by the JBIG Standard (ISO/IEC International Standard, "Coded Representation of Picture and Audio Information--Progressive Bi-level Image Compression Standard").
"Model templates define a neighborhood around a pixel to be coded. The values of the pixels in these neighborhoods, plus spatial phase in differential layers, define a context." Another example of a context model is given by the JPEG Standard (Digital Compression and Coding of Continuous-tone Still Images. ISO/IEC International Standard).
Since the context model is application specific, general coders are built by considering the probability estimation module and bit-stream generator only. Some probability estimation modules and bit-stream generators can be used interchangeably. Other probability estimation modules are dependent specifically on one particular bit-stream generator. For instance, IBM Q-coder is a combined probability estimation module and bit-stream generator. The B-coder is only a bit-stream generator. Therefore, the B-coder may be used with any probability estimation module.
One problem with decoders using binary entropy codes, such as IBM's Q-coder and the B-coder, is that they are slow, even in hardware implementation. Their operation requires a single large, slow feedback loop. To restate the decoding process, the context model uses past decoded data to produce a context. The probability estimation module uses the context to produce a probability class. The bit-stream generator uses the probability class and the compressed data to determine if the next bit is the likely or unlikely result. The probability estimation module uses the likely/unlikely result to produce a result bit (and to update the probability estimate for the context). The result bit is used by the context model to update its history of past data. All of these steps are required for decoding a single bit. Because the context model must wait for the result bit to update its history before it can provide the next context, the decoding of the next bit must wait. Therefore, parallel decoding of a single coded data stream does not occur in the prior art. It is desirable to decode data in parallel in order to increase the speed at which compressed data is decoded.
The present invention provides a lossless compression and decompression system. The present invention also provides a simple decoder which provides fast decoding. The present invention also provides a decoding system which decodes data in parallel. The present invention also provides an encoding system which encodes data such that it can be decoded in parallel.